#ifndef _BIN_SEARCH_TREE_
#define _BIN_SEARCH_TREE_
#include <utility> // For std::pair
#include <iostream>

enum Color {RED,BLACK};

//定义节点类
template<typename Key,typename T>
class Node {
public:
    std::pair<Key, T> data; // 键值对
    Node *left;
    Node *right;
    Node *p;

    Color color;
    

    Node(const std::pair<Key,T>& kval):data(kval){
        p = left = right = nullptr;
        color = RED; // 默认创建为红色方便插入
    };
private:
};

template<typename Key,typename T>
class RBTree {
public:
    T *find(const Key& key){
        Node<Key,T> *node = findNode(root,key);
        if(node){
            return &node->data.second;
        }
        return nullptr;
    }
    void insert(const std::pair<Key,T> & pair);
    void remove(const Key &key);
    void transplant(Node<Key,T> *u,Node<Key,T> *v);
    Node<Key,T> *getSuccessor(Node<Key,T> *node);
    // 中序遍历
    void inOrder(){
        inOrderTraversal(root);
    };

    void printRoot(){
        std::cout << root->data.first << " (" << (root->color == RED ? "RED" : "BLACK") << ") ";
    }
private:
    Node<Key,T> *root = nullptr;
    
    // 查找节点
    Node<Key,T> *findNode(Node<Key,T> *node, const Key &key);

    // 左旋
    void rotateLeft(Node<Key,T> * cur);
    // 右旋
    void rotateRight(Node<Key,T> * cur);

    // 插入调整
    void insertFix(Node<Key, T>* node);
    // 删除调整
    void deleteFix(Node<Key, T>* node) ;

    // 查找最小节点(最左边)
    Node<Key, T>* minimum(Node<Key, T>* node) ;

    void inOrderTraversal(Node<Key,T> *node);
};

//中序遍历
template<typename Key,typename T>
void RBTree<Key,T>::inOrderTraversal(Node<Key,T> *node){
    if(node != nullptr){
        inOrderTraversal(node->left);
        // std::cout << node->data.first << " (" << (node->color == RED ? "RED" : "BLACK") << ") ";
        inOrderTraversal(node->right);
    }
}

// 查找节点
template<typename Key,typename T>
Node<Key,T>* RBTree<Key,T>::findNode(Node<Key,T>* node,  const Key & key) {
    if (node == nullptr || node->key == key) {
        return node;
    }
    if (key < node->key) {
        return findNode(node->left, key);
    } else {
        return findNode(node->right, key);
    }
}

//左旋
template<typename Key,typename T>
void RBTree<Key,T>::rotateLeft(Node<Key,T> * cur_node){
    //旋转节点的右边节点
    Node<Key,T> *cur_right_node = cur_node->right;
    //旋转节点的父节点
    Node<Key,T> *cur_father = cur_node->p;
    //当前节点转下去之后，它之前的右节点的左节点和它要建立父子关系
    cur_node->right = cur_right_node->left;
    if(cur_right_node->left != nullptr){
        cur_right_node->left->p = cur_node;
    }
    cur_right_node->p = cur_father;
    if(cur_father != nullptr){
        if(cur_node == cur_father->left){
            cur_father->left = cur_right_node;
        }else {
            cur_father->right = cur_right_node;
        }   
    }else{
        //说明旋转点是根节点
        root = cur_right_node;
    }
    cur_node->p = cur_right_node;
    cur_right_node->left = cur_node;

}


//右旋
template<typename Key,typename T>
void RBTree<Key,T>::rotateRight(Node<Key,T> * cur_node){
    //旋转节点的右边节点
    Node<Key,T> *cur_left_node = cur_node->left;
    //旋转节点的父节点
    Node<Key,T> *cur_father = cur_node->p;
    //当前节点转下去之后，它之前的右节点的左节点和它要建立父子关系
    cur_node->left = cur_left_node->right;
    if(cur_left_node->right != nullptr){
        cur_left_node->right->p = cur_node;
    }
    cur_left_node->p = cur_father;
    if(cur_father != nullptr){
        if(cur_node == cur_father->left){
            cur_father->left = cur_left_node;
        }else {
            cur_father->right = cur_left_node;
        }   
    }else{
        //说明旋转点是根节点
        root = cur_left_node;
    }
    cur_node->p = cur_left_node;
    cur_left_node->right = cur_node;

}

//插入方法(对外)
template<typename Key,typename T>
void RBTree<Key,T>::insert(const std::pair<Key,T> & pair){
    Node<Key,T> *new_node = new Node<Key,T>(pair);
    Node<Key,T> *cur = root;
    Node<Key,T> *parent = nullptr; //记录每次寻找当前节点的父节点

    //首先查找插入点
    while(cur != nullptr){
        parent = cur;
        if(pair.first > cur->data.first){
            cur = cur->right;
        }else{
            cur = cur->left;
        }
    }
    //插入后，连接新节点的父节点
    new_node->p = parent;
    if(!parent){
        root = new_node;
    }else if(new_node->data.first > parent->data.first){
        parent->right = new_node;
    }else{
        parent->left = new_node;
    }

    new_node->color = RED;//插入的新节点默认红色
    insertFix(new_node);
}   

template<typename Key,typename T>
void RBTree<Key,T>::insertFix(Node<Key,T> * cur){

    while(true){
        //记录当前节点父节点
        Node<Key,T> *parent = cur->p;

        if(parent == nullptr || parent->color != RED){
            //没有父节点或者父节点是黑色
            break;
        }
        //记录当前节点祖父节点
        Node<Key,T> *grandf = parent->p;
        //如果祖父节点是不存在的，说明父节点是根节点,那么父亲变黑
        if(grandf == nullptr){
            parent->color = BLACK;
            break;
        }
        
        //记录当前节点叔叔节点
        Node<Key,T> *uncle = nullptr;
        //祖父节点也存在的情况下，分两种情况，叔叔黑和红,如下:
        //1.叔叔红，叔父爷变色，继续迭代上移，2.叔叔黑，根据LL,RR,LR,RL
        //父节点是左节点的时候
        if(parent == grandf->left){
            uncle = grandf->right;
            //叔叔节点存在，且红色
            if(uncle != nullptr && uncle->color == RED){
                uncle->color = BLACK;
                parent->color = BLACK;
                grandf->color = RED;
                cur = grandf;
            }else{//uncle不存在或者uncle是黑色，不存在也视为黑色
                if(cur == parent->right){//LR
                    //左旋变成LL型
                    cur = cur->p;
                    rotateLeft(cur);
                }
                //LL
                cur->p->color = BLACK;
                cur->p->p->color = RED;
                rotateRight(cur->p->p);
            }   
        }else{
            uncle = grandf->left;
            if(uncle != nullptr && uncle->color == RED){
                uncle->color = BLACK;
                parent->color = BLACK;
                grandf->color = RED;
                cur = grandf;
            }else{//uncle不存在或者uncle是黑色，不存在也视为黑色
                if(cur == parent->left){//RL
                    //左旋变成RR型
                    cur = cur->p;
                    rotateRight(cur);
                }
                //LL
                cur->p->color = BLACK;
                cur->p->p->color = RED;
                rotateLeft(cur->p->p);
            }
        }

    }
    root->color = BLACK; //确保根节点总是黑色
}


//删除接口(对外)
template<typename Key,typename T>
void RBTree<Key,T>::remove(const Key & key){
    //从根节点开始查询该值位置
    Node<Key,T> *cur = root;
    while(cur !=nullptr){
        if(key > cur->data.first){
            cur = cur->right;
        }else if(key < cur->data.first){
            cur = cur->left;
        }else{
            break;
        }
    }
    if(!cur) return;
    //记录最终被删除的点
    Node<Key,T> *need_delete = cur; 
    //记录最终被删除的点的颜色,因为需要根据被删除的节点是否是黑色决定是否要修复红黑树
    Color orignal_color = cur->color;
    /**
     * 定义replace_node记录最终顶替位置的节点，因为最终统一修复的时候需要从此节点开始看，此节点有需要处理的情况 
     * 如作为唯一的子节点，父节点被删除，那么自身肯定是红色，需要被记录，变黑，以及需要观察它的兄弟
     * */
    Node<Key,T> *replace_node ;
    //根据删除节点有几个孩子节点左二叉搜索树的删除
    if(cur->left == nullptr){
        //记录顶替的节点
        replace_node = cur->right;
        //右节点直接替换当前节点,然后变黑(变黑由后面统一处理)
        transplant(cur,cur->right);
    }else if(cur->right == nullptr){
        //左节点直接替换当前节点，然后变黑(变黑由后面统一处理)
        replace_node = cur->left;
        transplant(cur,cur->left);
    }else{

        //找后继结点替换,就转换成了删除后继节点的问题
        Node<Key,T> *successsor = getSuccessor(cur);
        //先替换值
        need_delete = successsor;
        cur->data = successsor->data;
        orignal_color = successsor->color;
        if(successsor->right){
            replace_node = successsor->right;
        }else{
            //后继节点没有子节点的时候，从后继节点本身开始查看兄弟节点
            replace_node = successsor;
        }
        //根据黑高和不红红性质，后继结点如果是黑有一个子节点，一定是红，后继是红，肯定没有子节点
        //然后删除后继节点,此时后继节点，此时必然后继节点只有右节点,则删除逻辑是用子节点代替自己
        transplant(successsor, successsor->right);
    }

    //如果最终被删除的是黑色,则需要调整,从被删除的子节点作为起点开始调整
    if (orignal_color == BLACK) {
        //有可能为空，因为可能出现删除节点没有子节点的情况
        deleteFix(replace_node);
    }
    //删除的是根
    if(need_delete == root){
        root = nullptr;
    }else{
        if(need_delete == need_delete->p->left){
            need_delete->p->left = nullptr;
        }else{
            need_delete->p->right = nullptr;
        }
    }
    delete need_delete;
}

//删除时修正
template<typename Key,typename T>
void RBTree<Key,T>::deleteFix(Node<Key,T> *cur){
		while (cur != root && cur->color != RED) {
			if (cur == cur->p->left) {
				Node<Key,T>* brother = cur->p->right;
                //1.兄弟红
				if (brother->color == RED) {
					brother->color = BLACK;
					cur->p->color = RED;
					rotateLeft(cur->p);
					brother = cur->p->right;//旋转之后重新获取bro，因为旋转后cur位置变化
				}
                //2.兄弟黑
                //兄弟两黑孩子
				if (brother->left->color != RED && brother->right->color != RED) {
					brother->color = RED;
					cur = cur->p;
				}//兄弟至少一个红孩子
				else {
                    //兄弟只有左红孩
					if (brother->right->color != RED) {
						brother->left->color = BLACK; 
						brother->color = RED; //变成单边RR的情况下面再处理
						rotateRight(brother);
						brother = cur->p->right;//旋转之后重新获取bro，因为旋转后cur位置变化
					}
                    //单边RR的情况
					brother->color = cur->p->color;
					cur->p->color = BLACK;
					brother->right->color = BLACK;
					rotateLeft(cur->p);
					cur = root;
				}
			}

			else {
				Node<Key,T>* brother = cur->p->left;

				if (brother->color == RED) {
					brother->color = BLACK;
					cur->p->color = RED;
					rotateRight(cur->p);
					brother = cur->p->left;
				}

				if (brother->left->color != RED && brother->right->color != RED) {
					brother->color = RED;
					cur = cur->p;
				}
				else {
					if (brother->left->color != RED) {
						brother->right->color = BLACK;
						brother->color = RED;
						rotateLeft(brother);
						brother = cur->p->left;
					}

					brother->color = cur->p->color;
					cur->p->color = BLACK;
					brother->left->color = BLACK;
					rotateRight(cur->p);
					cur = root;
				}
			}
		}
		cur->color = BLACK;
}

//替换，把u替换成v节点
//函数的作用是用一个子节点替换一个节点，但它默认了被替换的节点只有一个子节点
template<typename Key,typename T>
void RBTree<Key,T>::transplant(Node<Key,T> *u,Node<Key,T> *v){
    if(!u->p){
        root = v;
    }else if(u == u->p->left){
        u->p->left = v;
    }else{
        u->p->right = v;
    }
    if(v){
        v->p = u->p;
    }
}

//查询某节点的后继节点
template<typename Key,typename T>
Node<Key,T> * RBTree<Key,T>::getSuccessor(Node<Key,T> *cur){
    Node<Key,T> *temp = cur->right;
    while(temp->left){
        temp = temp->left;
    }
    return temp;
}




#endif